package datastructure.tree;

import java.util.Random;

/**
 * @author XY
 * @version 1.0
 * @date 2022/1/5 9:15
 * @Description
 */
public class Leet1576 {
    static class Solution {
        public String modifyString(String s) {
            if(s.equals("?")){
                return "a";
            }
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(c=='?'){
                    if(i==0){
                        char next = s.charAt(i + 1);
                        //97~122
                        Random random =new Random();
                        while(true){
                            int i1 = random.nextInt(122) % 26 + 97;
                            char a = (char)i1;
                            if(a != next){
                                s = s.replaceFirst("\\?", String.valueOf(a));
                                break;
                            }
                        }
                    }else if(i==s.length()-1){
                        char pre = s.charAt(i - 1);
                        Random random =new Random();
                        while(true){
                            int i1 = random.nextInt(122) % 26 + 97;
                            char a = (char)i1;
                            if(a != pre) {
                                s = s.replaceFirst("\\?", String.valueOf(a));
                                break;
                            }
                        }
                    }else{
                        char next = s.charAt(i + 1);
                        char pre = s.charAt(i - 1);
                        Random random =new Random();
                        while(true){
                            int i1 = random.nextInt(122) % 26 + 97;
                            char a = (char)i1;
                            if(a != next && a != pre) {
                                s = s.replaceFirst("\\?", String.valueOf(a));
                                break;
                            }
                        }
                    }
                }
            }
            return s;
        }
        /**
         * 在替换时，实际不需要遍历所有的小写字母，只需要遍历三个互不相同的字母，
         * 就能保证一定找到一个与前后字符均不相同的字母，
         * 在此我们可以限定三个不同的字母为 (‘a’,‘b’,‘c’)。
         *
         */
        public String modifyString1(String s) {
            int n = s.length();
            char[] arr = s.toCharArray();
            for (int i = 0; i < n; ++i) {
                if (arr[i] == '?') {
                    for (char ch = 'a'; ch <= 'c'; ++ch) {
                        //判断边界问题
                        if ((i > 0 && arr[i - 1] == ch) || (i < n - 1 && arr[i + 1] == ch)) {
                            continue;
                        }
                        arr[i] = ch;
                        break;
                    }
                }
            }
            return new String(arr);
        }
    }

    public static void main(String[] args) {
        Leet1576.Solution so = new Leet1576.Solution();
        System.out.println(so.modifyString1("??yw?ipkj?"));

    }
}
